11663 - GrayInc/11663.cpp

   1 /*
   2   Time limit exceeded!
   3
   4   I know the algorithm is fast enough (it's O(m * n)) but the implementation is slow
   5  */
   6 using namespace std;
   7 #include <algorithm>
   8 #include <iostream>
   9 #include <iterator>
  10 #include <sstream>
  11 #include <fstream>
  12 #include <cassert>
  13 #include <climits>
  14 #include <cstdlib>
  15 #include <cstring>
  16 #include <string>
  17 #include <cstdio>
  18 #include <vector>
  19 #include <cmath>
  20 #include <queue>
  21 #include <deque>
  22 #include <stack>
  23 #include <list>
  24 #include <map>
  25 #include <set>
  26
  27 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  28 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  29
  30 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  31 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  32 #define D(x) cout << #x " = " << (x) << endl
  33
  34 string next(const string &s);
  35 string prev(const string &s);
  36
  37 bool looksLike0000(const string &s){
  38   for (int i=0; i<s.size(); ++i) if (s[i] != '0') return false;
  39   return true;
  40 }
  41
  42 bool looksLike1000(const string &s){
  43   return s[0] == '1' && looksLike0000(s.substr(1));
  44 }
  45
  46 string next(const string &s){
  47   if (s.size() == 1) return s == "0" ? "1" : "0";
  48   string t = s.substr(1);
  49   if (s[0] == '0'){
  50     if (looksLike1000(t)){
  51       return "1" + t;
  52     }else{
  53       return "0" + next(t);
  54     }
  55   }else{
  56     if (looksLike0000(t)){
  57       return "0" + t;
  58     }else{
  59       return "1" + prev(t);
  60     }
  61   }
  62 }
  63
  64 string prev(const string &s){
  65   if (s.size() == 1) return s == "0" ? "1" : "0";
  66   string t = s.substr(1);
  67   if (s[0] == '0'){
  68     if (looksLike0000(t)){
  69       return "1" + t;
  70     }else{
  71       return "0" + prev(t);
  72     }
  73   }else{
  74     if (looksLike1000(t)){
  75       return "0" + t;
  76     }else{
  77       return "1" + next(t);
  78     }
  79   }
  80 }
  81
  82 int main(){
  83   int m;
  84   string s;
  85   while (cin >> m >> s && m){
  86     while (m--) s = next(s);
  87     cout << s << endl;
  88   }
  89   return 0;
  90 }